/**
 * 
 */
package leetCode;

import java.util.Arrays;

/**
 * @author zhongfang
 *
 */
public class ValidTriangleNumber {
    public int triangleNumber(int[] nums) {
    	int result=0;
    	Arrays.sort(nums);
    	for (int i = 0; i < nums.length; i++) {
			for (int j = i+1; j < nums.length; j++) {
				int sum=nums[i]+nums[j];
				//用二分法找到第一个满足条件的k:sum>n[k]&&sum<=n[k+1],result+=k+1-j
				result+=getMid(nums,sum,j);
			}
		}
    	return result;
    }
	private int getMid(int[] nums, int sum,int start) {
		int left=start+1,right=nums.length-1;
		while (left<=right) {
			int mid=(left+right)/2;
			if(nums[mid]<sum){
				if(mid==nums.length-1||nums[mid+1]>=sum){
					return mid-start;
				}else {//move right
					left=mid+1;
				}
			}else {//move left
				right=mid-1;
			}
		}
		return 0;
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] nums={0,1,0};
		System.out.println(new ValidTriangleNumber().triangleNumber(nums));
	}

}
